import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 */
class Solution {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node21 = new TreeNode(2);
        TreeNode node22 = new TreeNode(2);
        TreeNode node31 = new TreeNode(3);
        TreeNode node32 = new TreeNode(3);
        TreeNode node42 = new TreeNode(4);
        root.left = node21;
        root.right = node22;
        node21.right = node31;
        node22.left = node32;
        node22.right = node42;
        List<List<Integer>> list = zigzagLevelOrder(root);
        System.out.println(list.size());
    }

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        result.add(Collections.singletonList(root.val));
        List<TreeNode> nodeList = new ArrayList<>();
        nodeList.add(root);
        boolean goLeft = true;
        while (true) {
            List<Integer> valList = new ArrayList<>();
            List<TreeNode> newNodeList = new ArrayList<>();
            for (TreeNode node : nodeList) {
                if (node.left != null) {
                    valList.add(node.left.val);
                    newNodeList.add(node.left);
                }
                if (node.right != null) {
                    valList.add(node.right.val);
                    newNodeList.add(node.right);
                }
            }
            if (valList.isEmpty()) {
                break;
            }
            nodeList = newNodeList;
            if (goLeft) {
                Collections.reverse(valList);
            }
            result.add(valList);
            goLeft = !goLeft;
        }
        return result;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}